package TestSort;

import java.security.spec.RSAOtherPrimeInfo;
import java.util.Arrays;
import java.util.Random;

public class AllSort {

    public static int[] arr = new int[20_0000];

    public static void shellSort (int[] arr, int gap) {
        int i = 0;
        int j = gap;
        int tmp = gap;
        while (tmp != arr.length) {
            if (arr[i] > arr[j]) {
                swap(arr, j, i);
            }
            j = ++tmp;
            i = j - gap;
        }
    }

    public static int[] insertSort (int[] arr) {
        int j = 0;
        //i在j前面
        int i = j + 1;
        int tmp = i;
        //用i遍历数组
        while (i < arr.length) {
            while (j >= 0) {
                //找到比j下标小的值交换
                if (arr[tmp] < arr[j]) {
                    swap(arr, j, tmp);
                } else {
                    break;
                }
                tmp--;
                j--;
            }
            i++;
            tmp = i;
            j = i - 1;
        }
        return arr;
    }

    public static void selectSort () {
        int i = 0;
        int j = i + 1;
        int k = arr.length - 1;
        while (i < k) {
            int minIndex = i;
            int maxIndex = k;
            while (j < k) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
                j++;
            }
            swap(arr, minIndex, i);
            if (maxIndex == i) {
                maxIndex = minIndex;
            }
            swap(arr, maxIndex, k);
            i++;
            k--;
        }
    }

    public static void quickSort (int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = minNumIndex(arr, left, right);
        swap(arr, index, left);
        int pivot = partitionHole(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int minNumIndex (int[] arr, int left, int right) {
        int mid = (left + right) >> 1;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) {
                return left;
            } else {
                if (arr[mid] < arr[right]) {
                    return mid;
                } else {
                    return right;
                }
            }
        } else {
            if (arr[mid] < arr[right]) {
                return right;
            } else {
                if (arr[mid] < arr[left]) {
                    return mid;
                } else {
                    return left;
                }
            }
        }
    }

    public static int partitionHole (int[] arr, int left, int right) {
        /**
         * 先存下arr[left]的值
         * 这样left位置被替换了也没事
         */
        int pivot = arr[left];
        while (left < right) {
            //找到比pivot小的值
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //直接将小的值替换到left
            arr[left] = arr[right];
            //找到比pivot大的值
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //直接将大的值替换到right
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

    public static void heapSort (int[] arr) {
        createBigRootHeap(arr);
        int end = arr.length - 1;
        while (end >= 0) {
            swap(arr, end, 0);
            shiftDown(arr, 0, end);
            end--;
        }
    }

    public static void createBigRootHeap (int[] arr) {
        int parent = (arr.length - 2) / 2;
        while (parent >= 0) {
            shiftDown(arr, parent, arr.length);
            parent--;
        }
    }

    public static void shiftDown (int[] arr, int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    public static void swap (int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static long testQuickSort (int[] arr) {
        int[] tmpArr = Arrays.copyOf(arr, arr.length);
        long sTime = System.currentTimeMillis();
        quickSort(tmpArr, 0, tmpArr.length - 1);
        long eTime = System.currentTimeMillis();
        return eTime - sTime;
    }

    public static long testInsertSort (int[] arr) {
        int[] tmpArr = Arrays.copyOf(arr, arr.length);
        long sTime = System.currentTimeMillis();
        insertSort(tmpArr);
        long eTime = System.currentTimeMillis();
        return eTime - sTime;
    }

    public static long testShellSort (int[] arr) {
        int[] tmpArr = Arrays.copyOf(arr, arr.length);
        long sTime = System.currentTimeMillis();
        int gap = arr.length  - 1;
        while (gap > 0) {
            shellSort(tmpArr, gap);
            gap /= 2;
        }
        long eTime = System.currentTimeMillis();
        return eTime - sTime;
    }

    public static void main(String[] args) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(20_0000);
        }
        System.out.println("数据无序时，直接插入排序耗时:" + testInsertSort(arr) + "ms");
        System.out.println("数据无序时，希尔排序耗时:" + testShellSort(arr) + "ms");
        System.out.println("数据无序时，快速排序耗时:" + testQuickSort(arr) + "ms");
        System.out.println();
        int[] brr = new int[20_0000];
        for (int i = 0; i < brr.length; i++) {
            brr[i] = i;
        }
        System.out.println("数据有序时，直接插入排序耗时:" + testInsertSort(brr) + "ms");
        System.out.println("数据有序时，希尔排序耗时:" + testShellSort(brr) + "ms");
        System.out.println("数据有序时，快速排序耗时:" + testQuickSort(brr) + "ms");
    }
}
